from typing import List


class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [dict() for _ in range(n)]  # 以 i 为结尾公差为j的最长等差数列
        max_length = 1
        for i in range(n):
            for j in range(i):
                dp[i][nums[j] - nums[i]] = max(dp[i].get(nums[j] - nums[i], 1), dp[j].get(nums[j] - nums[i], 1) + 1)
                max_length = max(max_length, dp[i][nums[j] - nums[i]])
        return max_length


if __name__ == '__main__':
    s = Solution()
    r = s.longestArithSeqLength([83, 20, 17, 43, 52, 78, 68, 45])
    print(r)
